package com.hspedu.newData.dmsxl.滑动窗口;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-10 
 * @Version: 1.0
 */

public class LC76最小覆盖子串 {

    Map<Character,Integer> sm = new HashMap<>();
    Map<Character,Integer> tm = new HashMap<>();

    public String minWindow(String s, String t) {

        int tl = t.length();
        int sl = s.length();
        for (int i = 0; i < tl; i++) {
            tm.put(t.charAt(i),tm.getOrDefault(t.charAt(i),0)+1);
        }

        int low = 0;
        int len = Integer.MAX_VALUE;
        int x = 0;
        for (int i = 0; i < sl; i++) {
            if (tm.containsKey(s.charAt(i))){
                sm.put(s.charAt(i),sm.getOrDefault(s.charAt(i),0)+1);
            }

            while (check() && low <= i - tl + 1){

                if (len > i - low + 1){
                  x = low;
                  len = i - low + 1;
                }
                sm.put(s.charAt(low),sm.getOrDefault(s.charAt(low),0) - 1);
                low++;

            }
        }

        if (len > sl){
            return "";
        }
        return s.substring(x,x+len);
    }

    public boolean check(){
        for (Character c : tm.keySet()) {
            if (sm.getOrDefault(c,0) < tm.get(c)){
                return false;
            }
        }
        return true;
    }


    @Test
    public void test() {
        // 测试代码

//        String s = minWindow("ADOBECODEBANC", "ABC");
        String s1 = minWindow("a", "aa");
        System.out.println("111");
    }

}
